
//
// CS251
// Implementation of a HashTable that stores void *
//
#include "HashTableVoid.h"
#include <string.h>
#include <stdlib.h>

// Obtain the hash code of a key
int HashTableVoid::hash(const char * key)
{
	int sum = 0;
	char *p = (char*)key;
	for (unsigned int idx = 0; idx < sizeof(key)/sizeof(char); idx++, p++)
		sum += (idx + 1) * *p;
	return sum % TableSize;
}

// Constructor for hash table. Initializes hash table
HashTableVoid::HashTableVoid()
{
	_buckets = (HashTableVoidEntry**)malloc(TableSize*sizeof(HashTableVoidEntry));
	for (int idx = 0; idx < TableSize; idx++)
		_buckets[idx] = (HashTableVoidEntry*)malloc(sizeof(HashTableVoidEntry));
}

// Add a record to the hash table. Returns true if key already exists.
// Substitute content if key already exists.
bool HashTableVoid::insertItem( const char * key, void * data)
{
	int h = hash(key);
	HashTableVoidEntry *node = _buckets[h];
	HashTableVoidEntry *prev = NULL;
	while (node != NULL && node->_key != NULL && node->_data != NULL) {
		if (!strcmp(node->_key, key)) {
			node->_data = data;
			return true;
		}
		prev = node;
		node = node->_next;
	}
	node = new HashTableVoidEntry();
	node->_key = strdup(key);
	node->_data = data;
	node->_next = NULL;
	if (prev == NULL)
		_buckets[h] = node;
	else
		prev->_next = node;
	return false;
}

// Find a key in the dictionary and place in "data" the corresponding record
// Returns false if key is does not exist
bool HashTableVoid::find( const char * key, void ** data)
{
	int h = hash(key);
	HashTableVoidEntry *node = _buckets[h];
	if (node->_key == NULL)
		return false;
	while (node != NULL) {
		if (!strcmp(node->_key, key))
			break;
		node = node->_next;
	}
	if (node == NULL) {
		data = NULL;
		return false;
	}
	if (data != NULL)
		*data = (void**)node->_data;
	return true;
}

// Removes an element in the hash table. Return false if key does not exist.
bool HashTableVoid::removeElement(const char * key)
{
	int h = hash(key);
	HashTableVoidEntry *temp, *prev;
	if (find(key, NULL)) {
		temp = _buckets[h];
		while (temp->_next && !strcmp(temp->_key, key)) {
			prev = temp;
			temp = temp->_next;
		}
		if (prev != NULL)
			prev->_next = temp->_next;
		temp->_key = NULL;
		temp->_data = NULL;
		temp->_next = NULL;
		return true;
	}
	return false;
}

// Creates an iterator object for this hash table
HashTableVoidIterator::HashTableVoidIterator(HashTableVoid * hashTable)
{
	_hashTable = hashTable;
	_currentBucket = -1;
	_currentEntry = NULL;
}

// Returns true if there is a next element. Stores data value in data.
bool HashTableVoidIterator::next(const char * & key, void * & data)
{
	if (_currentBucket == -1 && _currentEntry == NULL) {
		_currentBucket = _hashTable->hash(key);
		_currentEntry = _hashTable->_buckets[_currentBucket];
	}
	if (!_hashTable->find(key, NULL)) {
		if (_currentEntry->_next != NULL) {
			_currentEntry = _currentEntry->_next;
			data = _currentEntry->_data;
			return true;
		}
		else {
			while (_currentEntry->_key == NULL && _currentBucket != _hashTable->TableSize - 1) {
				_currentBucket++;
				_currentEntry = _hashTable->_buckets[_currentBucket];
			}
			if (_currentBucket == _hashTable->TableSize) {
				data = NULL;
				return false;
			}
			data = _currentEntry->_data;
			return true;
		}
	}
	else {
		if (_currentEntry->_next == NULL) {
			data = _currentEntry->_data;
			return false;
		}
		data = _currentEntry->_data;
		_currentEntry = _currentEntry->_next;
		return true;
	}
}

